package MiddlePractice;

import java.util.LinkedList;

import org.junit.Test;

public class Demo394 {
//	394. 字符串解码
//	给定一个经过编码的字符串，返回它解码后的字符串。
//
//	编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
//
//	你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
//
//	此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
	
	public String decodeString(String s) {
		
		return myDecodeString(s.toCharArray(), 0, s.length()-1);
		
    }
	
	private String myDecodeString(char[] arr, int start, int end) {
		
		LinkedList<int[]> memo = new LinkedList<>();	//{次数， 内部串坐标}
		
		int l=0, r=0;
		int index = start;
		do {
			//如果发现是字符串  而不是数组+[...]  那就直接遍历  加入
			if(arr[index] >= 'a' && arr[index] <= 'z') {
				int leftLoc = index;
				while(index <= end && (arr[index] >= 'a' && arr[index] <= 'z')) {
					index++;
				}
				memo.add(new int[] {-1, leftLoc, index-1});
				//注意这里  把纯字符串部分标成-1  而不是1 
				//这是因为这个函数不好写递归终止条件
				//使用的终止条件就是  传进来的串  是一个纯字符串   这样的话就直接拼接字符返回串即可。
				//如果使用1  会导致函数无法区分这是不是纯字符串  就会对内部进一步递归  导致内存溢出
				continue;
			}
			
			//找前面的数字部分
			StringBuffer numChar = new StringBuffer();
			for(; arr[index] != '['; index++) {
				numChar.append(arr[index]);
			}
			int num = Integer.parseInt(numChar.toString());
			
			//算一个左括号
			l++;
			int leftLoc = index;	//记录左括号所在位置
			
			//找对应的那右括号的位置
			while(l != r) {
				index++;	//进入括号内部   来找括号的长度
				if(arr[index] == '[') {
					l++;
				} else if(arr[index] == ']'){
					r++;
				}
			}
			
			//跳出while后  index即为我们要找的那个右括号
			//加入备忘录
			int[] strArr = {num, leftLoc+1, index-1};	//注意加入的是括号内部的串
			memo.add(strArr);
			
			//index++进入下次寻找
			index++;
			
		} while(index <= end);
		
		
		//开始拼接字符串
		StringBuffer ans = new StringBuffer();
		
		for(int[] member : memo) {
			
			if(member[0] == -1) {
				ans.append(new String(arr, member[1], member[2]-member[1]+1));
			} else {
				String subStr = myDecodeString(arr, member[1], member[2]);
				for(int t=0; t<member[0]; t++) {
					ans.append(subStr);
				}
			}
		}
		
		return ans.toString();
		
	}
	
	@Test
	public void test_394() {
		String inp = "abc5[de2[fgh4[z]]]3[ij]lmn";
		System.out.println(myDecodeString(inp.toCharArray(), 0, inp.length()-1));
	}
}
